package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月17日
*时间：上午10:21:38
*/
public class Q518 {

    /**
     * @param n a positive integer
     * @param primes the given prime list
     * @return the nth super ugly number
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        if (primes == null || primes.length <= 0) {
            return 0;
        }
        if (n <= 1) {
            return 1;
        }
        int length = primes.length;
        int rs[] = new int[n];
        rs[0] = 1;
        int count[] = new int[length];
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < length; j++) {
                if (rs[count[j]] * primes[j] < min) {
                    min = rs[count[j]] * primes[j];
                }
            }
            for (int j = 0; j < length; j++) {
                if (min == rs[count[j]] * primes[j]) {
                    count[j]++;
                }
            }
            rs[i] = min;
        }
        return rs[n - 1];
    }

    @Test
    public void testA() {
        int[] primes = { 2, 7, 13, 19 };
        System.out.println(nthSuperUglyNumber(300, primes));
    }

}
